#include <stdio.h>
#include <stdlib.h>

#define SIZE_OF_ARRAY 10
typedef int ElemType_Tree;
// 二叉树
typedef struct BiTNode {
    ElemType_Tree data;
    struct BiTNode *lchild, *rchild;
}BiTNode, *BiTree;
// 存放二叉树元素的数组（静态数组）
typedef struct StaticArray {
    ElemType_Tree data[SIZE_OF_ARRAY];
    int length;
}StaticArray;
// 动态数组
typedef struct DynamicArray {
    ElemType_Tree *data;
    int length;
}DynamicArray;


/**
 * 数组静态初始化
 * @return
 */
void StaticInitArray(StaticArray array) {
    array.length = 0;
    for (int i = 0; i < SIZE_OF_ARRAY; ++i) {
        array.data[i] = 0;
    }
}

/**
 * 数组动态初始化
 * @param array
 * @param length
 */
void DynamicInitArray(DynamicArray &array, int length) {
    array.length = 0;
    array.data = (ElemType_Tree*) calloc(length, sizeof (ElemType_Tree));
}

/**
 * 插入二叉排序树
 * @param T
 * @param e
 * @return
 */
bool Create_BST(BiTree &T, ElemType_Tree e) {
    if (T == NULL) {
        BiTNode *tnew = (BiTNode*) calloc(1, sizeof (BiTNode));
        tnew->data = e;
        T = tnew;
        return true;
    }
    if (e == T->data) {
        // 与树中元素值相等的元素禁止入树
        return false;
    } else if (e < T->data) {
        return Create_BST(T->lchild, e);
    } else {
        return Create_BST(T->rchild, e);
    }
}
/**
 * 中序遍历二叉树，并记录到数组
 * @param T
 */
void InOrder(BiTree T, DynamicArray &array) {
    if (T != NULL) {
        InOrder(T->lchild, array);
        printf("%3d", T->data);
        array.data[array.length++] = T->data;
        InOrder(T->rchild, array);
    }
}

/**
 * 折半查找数组中元素的下标
 * @param array
 * @param e
 * @return
 */
int Binary_Search(DynamicArray array, ElemType_Tree e) {
    int low = 0, high = array.length - 1;
    int mid;
    while (low <= high) {
        mid = (low + high) / 2;
        if (array.data[mid] == e) {
            return mid;
        } else if (array.data[mid] < e) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    return -1;
}

/**
 * 读取10个元素 87  7 60 80 59 34 86 99 21  3，然后建立二叉查找树，中序遍历输出3  7 21 34 59 60 80 86 87 99，
 * 针对有序后的元素，存入一个长度为10的数组中，通过折半查找找到21的下标（下标为2），然后输出2
 * @return
 */
int main() {

    BiTree T = NULL;
    DynamicArray bstArray;
    DynamicInitArray(bstArray, SIZE_OF_ARRAY);

    // 建立二叉排序树
    for (int i = 0; i < 10; ++i) {
        ElemType_Tree e;
        scanf("%d", &e);
        if (!Create_BST(T, e)) {
            printf("插入元素%d失败..\n", e);
        }
    }

    // 中序遍历二叉树
    InOrder(T, bstArray);
    printf("\n");

    // 折半查找 元素21的下标
    int index = Binary_Search(bstArray, 21);
    printf("%d\n", index);

    return 0;
}